package io.gitee.wiqer.simple;

import io.gitee.wiqer.ListNode;

import java.util.Arrays;

public class SolutionNC70_SortInList {
    /**
     *给定一个节点数为n的无序单链表，对其按升序排序。
     *
     * 数据范围：0 < n \le 1000000<n≤100000
     * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head == null){
            return null;
        }
        //查找链表长度
        ListNode cur = head;
        int length = 0;
        while(cur != null){
            length++;
            cur = cur.next;
        }
        //将链表的值放入到数组中并进行排序
        int[] arr = new int[length];
        ListNode cur1 = head;
        for(int i = 0; i < arr.length; i++){
            arr[i] = cur1.val;
            cur1 = cur1.next;
        }
        Arrays.sort(arr);
        //将数组的值再放入到聊表中
        ListNode cur2 = head;
        for(int i = 0; i<arr.length; i++){
            cur2.val = arr[i];
            cur2 = cur2.next;
        }
        return head;
    }
}
